{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Common Subsequence Between Sorted Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestCommonSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #排序数组之间的最长公共子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由整数数组组成的数组<code>arrays</code>，其中<code>arrays[i]</code>是严格递增排序的，返回一个表示所有数组之间的最长公共子序列的整数数组。</p>\n",
    "\n",
    "<p>子序列是从另一个序列派生出来的序列，删除一些元素或不删除任何元素，而不改变其余元素的顺序。</p>\n",
    "\n",
    "<p><strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> arrays = [[<strong><em>1</em></strong>,3,<strong><em>4</em></strong>],\n",
    "               [<strong><em>1</em></strong>,<strong><em>4</em></strong>,7,9]]\n",
    "<strong>输出:</strong> [1,4]\n",
    "<strong>解释:</strong> 这两个数组中的最长子序列是[1,4]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> arrays = [[<strong><em>2</em></strong>,<strong><em>3</em></strong>,<strong><em>6</em></strong>,8],\n",
    "               [1,<strong><em>2</em></strong>,<strong><em>3</em></strong>,5,<strong><em>6</em></strong>,7,10],\n",
    "               [<strong><em>2</em></strong>,<strong><em>3</em></strong>,4,<em><strong>6</strong></em>,9]]\n",
    "<strong>输出:</strong> [2,3,6]\n",
    "<strong>解释:</strong> 这三个数组中的最长子序列是[2,3,6]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> arrays = [[1,2,3,4,5],\n",
    "               [6,7,8]]\n",
    "<strong>输出:</strong> []\n",
    "<strong>解释:</strong> 这两个数组之间没有公共子序列。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>限制条件:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= arrays.length <= 100</code></li>\n",
    "\t<li><code>1 <= arrays[i].length <= 100</code></li>\n",
    "\t<li><code>1 <= arrays[i][j] <= 100</code></li>\n",
    "\t<li><code>arrays[i]</code> 是严格递增排序.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-common-subsequence-between-sorted-arrays](https://leetcode.cn/problems/longest-common-subsequence-between-sorted-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-common-subsequence-between-sorted-arrays](https://leetcode.cn/problems/longest-common-subsequence-between-sorted-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3,4],[1,4,7,9]]', '[[2,3,6,8],[1,2,3,5,6,7,10],[2,3,4,6,9]]', '[[1,2,3,4,5],[6,7,8]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        return sorted(reduce(lambda x, y: set(x) & set(y), arrays))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # set\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        cur = set(arrays[0])\n",
    "        for i in range(1, len(arrays)):\n",
    "            cur &= set(arrays[i])\n",
    "\n",
    "        return sorted(list(cur))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        res = set(arrays[0])\n",
    "        for array in arrays[1:]:\n",
    "            res = res.intersection(array)\n",
    "        return sorted(list(res))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        counter = [0] * 101\n",
    "        n = len(arrays)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            for j in arrays[i]:\n",
    "                counter[j] += 1\n",
    "        for i in range(101):\n",
    "            if counter[i] == n: res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        n = len(arrays)\n",
    "        counter = Counter(arrays[0])\n",
    "        for i in range(1, n):\n",
    "            counter += Counter(arrays[i])\n",
    "        filter_counter = list(filter(lambda x: x[1] == n, counter.items()))\n",
    "        return [x[0] for x in filter_counter]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        cur = set(arrays[0])\n",
    "        for i in range(1,len(arrays)):\n",
    "            cur &= set(arrays[i])\n",
    "\n",
    "        if not cur:\n",
    "            return []\n",
    "\n",
    "        return sorted(list(cur))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        counter = defaultdict(int)\n",
    "        for arr in arrays:\n",
    "            for it in arr:\n",
    "                counter[it] += 1\n",
    "        result = list()\n",
    "        n = len(arrays)\n",
    "        for i in range(1, 101):\n",
    "            if counter[i] == n:\n",
    "                result.append(i)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        return sorted(reduce(lambda x, y: x & y, map(set,arrays)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # set\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        cur = set(arrays[0])\n",
    "        for i in range(1,len(arrays)):\n",
    "            cur &= set(arrays[i])\n",
    "\n",
    "        return sorted(list(cur))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "        n=len(arrays)\n",
    "        for i in range(1,101):\n",
    "            check=True\n",
    "            for j in range(n):\n",
    "                m=len(arrays[j])\n",
    "                temp=bisect_left(arrays[j],i)\n",
    "                if temp>=m or arrays[j][temp]!=i:\n",
    "                    check=False\n",
    "            if check:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "\n",
    "        dp=[[0]*100 for i in range(len(arrays))]\n",
    "\n",
    "        for i in range(len(arrays)):\n",
    "            for j in arrays[i]:\n",
    "                dp[i][j-1]=1\n",
    "        result=[]\n",
    "        for j in range(100):\n",
    "            num=0\n",
    "            for i in range(len(arrays)):\n",
    "                num+=dp[i][j]\n",
    "            if num==len(arrays):\n",
    "                result.append(j+1)\n",
    "\n",
    "        return result\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        for arr in arrays:\n",
    "            if not arr:\n",
    "                return []\n",
    "        n = len(arrays)\n",
    "        if n == 1:\n",
    "            return arrays[0]\n",
    "        elif n == 2:\n",
    "            arr1,arr2 = arrays[0], arrays[1]\n",
    "            n1,n2 = len(arr1), len(arr2)\n",
    "            i=j = 0\n",
    "            ans = []\n",
    "            while i < n1 and j<n2:\n",
    "                if arr1[i] < arr2[j]:\n",
    "                    i += 1\n",
    "                elif arr1[i] == arr2[j]:\n",
    "                    ans.append(arr1[i])\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            return ans \n",
    "        else:\n",
    "            return self.longestCommonSubsequence([self.longestCommonSubsequence(arrays[:n//2]), self.longestCommonSubsequence(arrays[n//2:])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "\n",
    "        cnts = [0] * 101\n",
    "        for arr in arrays:\n",
    "            for num in arr:\n",
    "                cnts[num] += 1\n",
    "\n",
    "        n = len(arrays)\n",
    "        return [i for i in range(1,101) if cnts[i] == n]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def find(arr1, arr2):\n",
    "            n1,n2 = len(arr1), len(arr2)\n",
    "            i=j = 0\n",
    "            ans = []\n",
    "            while i < n1 and j<n2:\n",
    "                if arr1[i] < arr2[j]:\n",
    "                    i += 1\n",
    "                elif arr1[i] == arr2[j]:\n",
    "                    ans.append(arr1[i])\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            return ans \n",
    "        \n",
    "        cur = arrays[0]\n",
    "        for arr in arrays[1:]:\n",
    "            cur = find(cur, arr)\n",
    "            if not cur:\n",
    "                break  \n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:\n",
    "        a=[j for i in arrays for j in i]\n",
    "        b=collections.Counter(a)\n",
    "        result=[]\n",
    "        for key in b:\n",
    "            if b[key]==len(arrays):\n",
    "                result.append(key)\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
